package com.learn.algorithm;

public class BitOperation {

    /**
     * 非负数返回1
     * 负数返回0
     */
    public static int sign(int n) {
        return flip(n >>> 31);
    }

    /**
     * 0 -> 1
     * 1 -> 0
     *
     * @param n 必须是0或1
     */
    public static int flip(int n) {
        return n ^ 1;
    }

    /**
     * 可能溢出的版本
     */
    public static int getMax1(int a, int b) {
        int c = a - b;
        int signA = sign(c);
        int signB = flip(signA);
        return signA * a + signB * b;
    }

    public static int getMax2(int a, int b) {
        int c = a - b;
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);

        int sameAB = sa ^ sb;
        int returnA = (sameAB == 0 && sc == 1) ? 1 : 0;
        int returnB = flip(returnA);

        return returnA * a + returnB * b;
    }

    public static void exchange(int[] array, int i, int j) {
        if (i != j) {
            array[i] ^= array[j];
            array[j] ^= array[i];
            array[i] ^= array[j];
        } else {
            Sort.swap(array, i, j);
        }
    }

    /**
     * 0-10 这11个数字中任意去掉一个放入长度10的数组 找到去掉的那个数字
     */
    public static int findMissingNumber(int[] array) {
        int eor1 = 0;
        int eor2 = 0;
        for (int i = 0; i < array.length; i++) {
            eor1 ^= array[i];
            eor2 ^= i;
        }
        eor2 ^= 10;
        return eor1 ^ eor2;
    }

    /**
     * 数组中有一个数字出现奇数次, 其他所以数字出现偶数次, 找到出现奇数次的数并返回
     *
     * @param array 数组
     */
    public static int findSingleNumber(int[] array) {
        int eor = 0;
        for (int k : array) {
            eor ^= k;
        }
        return eor;
    }

    /**
     * 提取一个数字最右侧的二进制位, 其他位设置为0
     * 如 01101101 -> 00000001
     * 如 01101110 -> 00000010
     */
    public static int extractRightOne(int a) {
        // a & (^a + 1)
        // a & (-a)
        return a & (-a);
    }

    /**
     * 数组中有2个数出现了奇数次, 其他数都出现偶数次, 找到出现奇数次的两个数
     */
    public static int[] singleNumber2(int[] array) {
        int eor1 = 0;
        for (int num : array) {
            eor1 ^= num;
        }
        int rightOne = extractRightOne(eor1);
        int eor2 = 0;
        // 用最右侧是否是1把两个出现奇数次的数分开
        for (int num : array) {
            if ((num & rightOne) == 0) {
                eor2 ^= num;
            }
        }
        return new int[]{eor2, (eor1 ^ eor2)};
    }

    /**
     * 数组中有一个数出现的次数少于m次 其余数字出现的次数都是m次 找出出现次数少于m次的数
     */
    public static int lessThanM(int[] array, int m) {
        int[] cnts = new int[32];
        for (int num : array) {
            for (int i = 0; i < 32; i++) {
                cnts[i] += ((num >> i) & 1);
            }
        }
        int answer = 0;
        for (int i = 0; i < cnts.length; i++) {
            if ((cnts[i] % m) != 0) {
                answer |= 1 << i;
            }
        }
        return answer;
    }

    // 判断一个数是不是2的整数次幂
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
//        return n == extractRightOne(n);
//        return ((n & (n - 1)) == 0);
        return n > 0 && (n == (n & -n));
    }

    // 判断一个数是不是3的整数次幂
    public static boolean isPowerOfThree(int n) {
        // 3^19次方是整数范围内3的最大次幂
        return n > 0 && ((int) Math.pow(3, 19) % n) == 0;
    }

    /**
     * 返回大于或等于n的最小的2的幂
     * 如果int范围内不存在，则返回整数最小值
     */
    public static int nearestPowerOfTwo(int n) {
        if (n <= 0) {
            return 1;
        }
        n--;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n + 1;
    }

    /**
     * 计算区间内所有数字的与运算的值
     * right 不断被去掉最右侧的1，直到小于等于left
     * https://leetcode.cn/problems/bitwise-and-of-numbers-range/
     */
    public static int isPowerOfTwo2(int left, int right) {
        while (left < right) {
            right -= extractRightOne(right);
        }
        return right;
    }

    /**
     * 将一个数的二进制位逆序后返回
     * 1. 相邻的两个位互换
     * 2. 相邻的四个位互换
     * 3. 相邻的八个位互换
     * 4. 相邻的十六位互换
     */
    public static int reverseBits(int n) {
//        n = ((n & 0b10101010101010101010101010101010) >>> 1 | ((n & 0b01010101010101010101010101010101) << 1));
//        n = ((n & 0b11001100110011001100110011001100) >>> 2 | ((n & 0b00110011001100110011001100110011) << 2));
//        n = ((n & 0b11110000111100001111000011110000) >>> 4 | ((n & 0b00001111000011110000111100001111) << 4));
//        n = ((n & 0b11111111000000001111111100000000) >>> 8 | ((n & 0b00000000111111110000000011111111) << 8));
        n = ((n & 0xaaaaaaaa) >>> 1 | ((n & 0x55555555) << 1));
        n = ((n & 0xcccccccc) >>> 2 | ((n & 0x33333333) << 2));
        n = ((n & 0xf0f0f0f0) >>> 4 | ((n & 0x0f0f0f0f) << 4));
        n = ((n & 0xff00ff00) >>> 8 | ((n & 0x00ff00ff) << 8));
        n = (n >>> 16) | (n << 16);
        return n;
    }

    /**
     * 计算一个整数的二进制位中1的个数
     */
    public static int oneCount(int n) {
        int ans = 0;
        while (n != 0) {
            ans++;
            n &= (n - 1);
        }
        return ans;
    }

    /**
     * 使用位运算实现加法
     */
    public static int add(int a, int b) {
        // 1. 做无进位的加法
        // 2. 进位信息
        // 3. 无进位加法的结果再加上进位信息左移1位
        // 重复整个过程
        int ans = a;
        while (b != 0) {
            ans = a ^ b;      // 计算无进位加法
            b = (a & b) << 1; // 计算进位信息
            a = ans;          // 无进位加法的结果加进位信息
        }
        return ans;
    }

    public static int negative(int a) {
        return add(~a, 1);
    }

    /**
     * 使用位运算实现减法
     */
    public static int minus(int a, int b) {
        // 将减法转化为加法 -b = + (-b)
        return add(a, negative(b));
    }

    public static int multiply(int a, int b) {
        int ans = 0;
        while (b != 0) {
            // b的二进制最右1位是否是1
            if ((b & 1) != 0) {
                ans = add(a, ans);
            }
            a <<= 1;
            b >>>= 1;
        }
        return ans;
    }

    public static void main(String[] args) {
        int a = Integer.MIN_VALUE;
        int b = Integer.MAX_VALUE;
        System.out.println(getMax2(a, b));
        int[] array1 = new int[]{0, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(findMissingNumber(array1));
        int[] array2 = new int[]{0, 2, 0, 2, 1};
        System.out.println(findSingleNumber(array2));
        System.out.println(extractRightOne(6));
        int[] array3 = new int[]{1, 2, 3, 3, 5, 5, 7, 7, 9, 9};
        Sort.print(singleNumber2(array3));

        System.out.println((int) Math.pow(3, 19));
        System.out.println(oneCount(7));

        System.out.println(multiply(25, - 25));
    }
}
